//************************************************************
//    > File Name: addlists.cpp
//    > Author: davis
//    > Mail:  
//    > Created Time: 2017年03月17日 11:12:31
//***********************************************************
//lintcode #167
#include<bits/stdc++.h>
using namespace std;
struct ListNode{
	int val;
	ListNode *next;
	ListNode(int x=-1) : val(x),next(NULL) {}
/*	~ListNode() {
		if(next) delete next;
	}*/
};

ListNode *addlists(ListNode *l1,ListNode *l2){
	ListNode H(-1),*p;
	int dec=10,carry=0;
	for(p=&H;l1 && l2;l1=l1->next,l2=l2->next){
		p->next = new ListNode(l1->val+l2->val+carry);
		p=p->next;
		carry=(p->val)/dec;
		p->val=(p->val)%dec;
	}
	for(;l1;l1=l1->next){
		p->next = new ListNode(l1->val+carry);
		p=p->next;
		carry=(p->val)/dec;
		p->val=(p->val)%dec;
	}
	for(;l2;l2=l2->next){
		p->next = new ListNode(l2->val+carry);
		p=p->next;
		carry=(p->val)/dec;
		p->val=(p->val)%dec;
	}
	if(carry)
		p->next = new ListNode(carry);
	return H.next;
}

ListNode *create(vector<int> &v){
	ListNode H;
	int i=0;
	for(ListNode *p=&H;i<v.size();++i){
		p->next=new ListNode(v[i]);
		p=p->next;
	}
	return H.next;
}
/*
ListNode *create2(vector<int> &v){
	ListNode H, *p;
	int i=0;
	for(p=&H;i<v.size();++i){
		p->next = new ListNode(v[i]);
		p=p->next;
	}
	p = H.next;
	H.next=NULL;
	return p;
}
*/

void clean(ListNode *l){
	for(ListNode *t;l;){
		t = l;
		l=l->next;
		delete t;
	}
}
int main()
{
	ListNode a[3];
	a[0].val=7, a[0].next=&a[1];
	a[1].val=1, a[1].next=&a[2];
	a[2].val=6, a[2].next=NULL;

	ListNode *b = new ListNode(5);
	b->next = new ListNode(9);
	b->next->next = new ListNode(2);

	ListNode *c=new ListNode[3];
	c[0].val=7,c[0].next=&c[1];
	c[1].val=1,c[1].next=&c[2];
	c[2].val=6,c[2].next=NULL;

	vector<int> v={
		7,1,6
	};
	ListNode *d=create(v);
	
	//ListNode *t=addlists(a,b);
	//ListNode *t=addlists(c,b);
	ListNode *t=addlists(d,b);
	for(;t;t=t->next)
		cout<<t->val<<" ";
	cout<<endl;

	clean(d);

	for(ListNode *temp;b;){
		temp=b;
		b=b->next;
		delete temp;
	}

	for(ListNode *temp;t;){
		temp=t;
		t=t->next;
		delete temp;
	}

	delete []c;

	return 0;
}

//219
